#include <iostream>
#include <vector>
using namespace std;

/* @brief 求一个子矩阵的和
 *
 * @param arr: 二维数组指针
 * @param row_head: 起始行
 * @param row_tail: 结束行
 * @param col_head: 起始列
 * @param col_tail: 结束列
 *
 */
int sum_of_submat(int** arr, int row_head, int row_tail, int col_head,
                  int col_tail) {
  int sum = 0;
  for (int i = row_head; i <= row_tail; i++) {
    for (int j = col_head; j <= col_tail; j++) {
      sum += arr[i][j];
    }
  }
  return sum;
}

/* @brief 求最大子矩阵的和(暴力遍历)
 *  外面四层循环，中间求和需要两层循环，复杂度 O(n^6)
 *
 * @param arr: 二维数组指针
 * @param row_head: 起始行
 * @param row_tail: 结束行
 * @param col_head: 起始列
 * @param col_tail: 结束列
 *
 */
int max_submat_bf(int** arr, int row_head, int row_tail, int col_head,
                  int col_tail) {
  int ans = 0;
  for (int ri = row_head; ri <= row_tail; ri++) {
    for (int rj = ri; rj <= row_tail; rj++) {
      for (int ci = col_head; ci <= col_tail; ci++) {
        for (int cj = ci; cj <= col_tail; cj++) {
          int sum = sum_of_submat(arr, ri, rj, ci, cj);
          if (sum > ans) ans = sum;
        }
      }
    }
  }
  return ans;
}
 
/* @brief 求最大子矩阵的和(动态规划)
 *   
 *
 * @param arr: 二维数组指针
 * @param row_head: 起始行
 * @param row_tail: 结束行
 * @param col_head: 起始列
 * @param col_tail: 结束列
 *
 */
int max_submat_dp(int** arr, int row_head, int row_tail, int col_head,
                  int col_tail) {
  int ans = 0;
  
  return ans;
}

int main(int argc, char** argv) {
  int arr[] = {1, -2, 3, -4, 5, -6};
  cout << max_subseq_dp(arr, 0, sizeof(arr) / sizeof(int) - 1) << endl;
  int arr2[] = {1, 2, 3, 4, 5, 6};
  cout << max_subseq_dp(arr2, 0, sizeof(arr2) / sizeof(int) - 1) << endl;
}